package month1;

import java.util.Arrays;

public class SearchRange34_07 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)));
    }

    static int[] searchRange(int[] nums, int target) {
        int l = binarySearch(nums, target, true), r = binarySearch(nums, target, false) - 1;
        if (l <= r && r < nums.length && nums[l] == target && nums[r] == target) {
            return new int[]{l, r};
        }
        return new int[]{-1, -1};
    }

    static int binarySearch(int[] nums, int target, boolean low) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while(l <= r) {
            int m = l + r >> 1;
            if (nums[m] > target || low && nums[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}
